{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Trim a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trimBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #修剪二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉搜索树的根节点 <code>root</code> ，同时给定最小边界<code>low</code> 和最大边界 <code>high</code>。通过修剪二叉搜索树，使得所有节点的值在<code>[low, high]</code>中。修剪树 <strong>不应该</strong>&nbsp;改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在&nbsp;<strong>唯一的答案</strong>&nbsp;。</p>\n",
    "\n",
    "<p>所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/09/trim1.jpg\" style=\"height: 126px; width: 450px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,2], low = 1, high = 2\n",
    "<strong>输出：</strong>[1,null,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/09/trim2.jpg\" style=\"height: 277px; width: 450px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,0,4,null,2,null,null,1], low = 1, high = 3\n",
    "<strong>输出：</strong>[3,2,null,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>树中每个节点的值都是 <strong>唯一</strong> 的</li>\n",
    "\t<li>题目数据保证输入是一棵有效的二叉搜索树</li>\n",
    "\t<li><code>0 &lt;= low &lt;= high &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [trim-a-binary-search-tree](https://leetcode.cn/problems/trim-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [trim-a-binary-search-tree](https://leetcode.cn/problems/trim-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2]\\n1\\n2', '[3,0,4,null,2,null,null,1]\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        if root.val < low:\n",
    "            return root.right\n",
    "        if root.val > high:\n",
    "            return root.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\r\n",
    "        if not root:\r\n",
    "            return\r\n",
    "        if root.val < low:\r\n",
    "            root = self.trimBST(root.right, low, high)\r\n",
    "        elif root.val > high:\r\n",
    "            root = self.trimBST(root.left, low, high)\r\n",
    "        else:    \r\n",
    "            root.left = self.trimBST(root.left, low, high)\r\n",
    "            root.right = self.trimBST(root.right, low, high)\r\n",
    "        return root\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "#这里的思想是先裁剪子树。\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        if root.val < low or root.val > high:\n",
    "            if not root.left and not root.right:\n",
    "                return None\n",
    "            elif root.left and not root.right:\n",
    "                return root.left\n",
    "            elif root.right and not root.left:\n",
    "                return root.right\n",
    "            else:\n",
    "                curr = root.right\n",
    "                while(curr):\n",
    "                    curr = curr.left\n",
    "                curr.left = root.left\n",
    "                return root.right\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        inorder_arr = []\n",
    "        self.inorder(root, inorder_arr)\n",
    "        # print(inorder_arr)\n",
    "        for val in inorder_arr: \n",
    "            if val < low or val > high:\n",
    "                root = self.deleteNode(root, val)\n",
    "        \n",
    "        return root \n",
    "    \n",
    "    def deleteNode(self, root: Optional[TreeNode], val) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return \n",
    "        \n",
    "        if root.val == val:\n",
    "            if root.left is None and root.right is None:\n",
    "                return None \n",
    "            elif root.left and root.right is None:\n",
    "                return root.left \n",
    "            elif root.right and root.left is None:\n",
    "                return root.right \n",
    "            else: \n",
    "                cur = root.right\n",
    "                while cur.left:\n",
    "                    cur = cur.left \n",
    "                cur.left = root.left \n",
    "                return root.right \n",
    "        elif root.val > val:\n",
    "            root.left = self.deleteNode(root.left, val)\n",
    "            return root\n",
    "        else:\n",
    "            root.right = self.deleteNode(root.right, val)\n",
    "            return root \n",
    "    \n",
    "    def inorder(self, root: Optional[TreeNode], res: List) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return \n",
    "        \n",
    "        self.inorder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorder(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            root.left = None\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            root.right = None\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        \n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def putIntoLeft(root,node):\n",
    "            if root.left == None:\n",
    "                root.left = node\n",
    "                return \n",
    "            putIntoLeft(root.left,node)\n",
    "\n",
    "\n",
    "\n",
    "        def process(root):\n",
    "            if root == None:\n",
    "                return None \n",
    "            left = process(root.left)\n",
    "            right = process(root.right)\n",
    "            root.left = left \n",
    "            root.right = right\n",
    "            if root.val >= low and root.val <= high:\n",
    "                return root \n",
    "            else:\n",
    "                if left == None and right == None:\n",
    "                    return None \n",
    "                elif left == None:\n",
    "                    return right \n",
    "                elif right == None:\n",
    "                    return left \n",
    "                else:\n",
    "                    putIntoLeft(right,left)\n",
    "                    return right \n",
    "        node = process(root)\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 BST 的 root\n",
    "        以及最低和最高的邊界數值: low, high\n",
    "        修剪這個 BST, 讓這個 BST 的數值就在 low ~ high 之間\n",
    "        修剪的時候不可以破壞它們的結構\n",
    "        回傳修剪之後的 root, root 也有可能會因為 low, high 而改變\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        # 先往兩邊往下鑽\n",
    "        root.left  = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        # 如果當前這個數值不在 low~high 的範圍, 代表這個 root 要被取代了\n",
    "        if not low <= root.val <= high:\n",
    "            if root.left:\n",
    "                root = root.left\n",
    "            elif root.right:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = None\n",
    "        return root\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        root.left = self.trimBST(root.left,low,high)\n",
    "        root.right = self.trimBST(root.right,low,high)\n",
    "        if root.val < low:\n",
    "            return root.right\n",
    "        if root.val > high:\n",
    "            return root.left\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val < low:\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "            return root.right\n",
    "        if root.val > high:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            return root.left\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val < low:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = None\n",
    "            elif node.val > high:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = None\n",
    "            return node\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        elif root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def deleteNode(self, root: Optional[TreeNode], low, high) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.deleteNode(root.left, low, high)\n",
    "        root.right = self.deleteNode(root.right, low, high)\n",
    "\n",
    "        if root.val < low or root.val > high:\n",
    "            if root.left == None:\n",
    "                return root.right\n",
    "            if root.right == None:\n",
    "                return root.left\n",
    "            \n",
    "\n",
    "        return root\n",
    "\n",
    "    # def getMin(self, node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "    #     while node.left != None and node.:\n",
    "    #         node = node.left\n",
    "    #     return node\n",
    "    \n",
    "    # def getMax(self, node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "    #     while node.right != None:\n",
    "    #         node = node.right\n",
    "    #     return node\n",
    "\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        root = self.deleteNode(root, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 BST 的 root\n",
    "        以及最低和最高的邊界數值: low, high\n",
    "        修剪這個 BST, 讓這個 BST 的數值就在 low ~ high 之間\n",
    "        修剪的時候不可以破壞它們的結構\n",
    "        回傳修剪之後的 root, root 也有可能會因為 low, high 而改變\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        root.left  = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        if not low <= root.val <= high:\n",
    "            if root.left:\n",
    "                root = root.left\n",
    "            elif root.right:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = None\n",
    "        return root\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        if root.val >= low and root.val <= high:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "            return root\n",
    "        elif root.val > high and root.val >= low:\n",
    "            \n",
    "            if root.left is not None:\n",
    "                root.left = self.trimBST(root.left, low, high)\n",
    "            return root.left\n",
    "        elif root.val < low and root.val <= high:\n",
    "            if root.right is not None:\n",
    "                \n",
    "                root.right = self.trimBST(root.right, low, high)\n",
    "            return root.right\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self,root,key):\n",
    "        if not root:\n",
    "            return root\n",
    "        if key == root.val:\n",
    "            if not root.left and not root.right:\n",
    "                return None\n",
    "            elif not root.left and root.right:\n",
    "                return root.right\n",
    "            elif root.left and not root.right:\n",
    "                return root.left\n",
    "            else:\n",
    "                cur = root.left\n",
    "                while cur.right:\n",
    "                    cur = cur.right\n",
    "                cur.right = root.right\n",
    "                return root.left\n",
    "\n",
    "        if key < root.val:\n",
    "            root.left = self.deleteNode(root.left,key)\n",
    "        if key > root.val:\n",
    "            root.right = self.deleteNode(root.right,key)\n",
    "        return root\n",
    "\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return []\n",
    "        deleteList = []\n",
    "        def midSearch(cur):\n",
    "            if not cur:\n",
    "                return \n",
    "            midSearch(cur.left)\n",
    "            if cur.val < low or cur.val > high:\n",
    "                deleteList.append(cur.val)\n",
    "            midSearch(cur.right)\n",
    "        midSearch(root)\n",
    "        for i in deleteList:\n",
    "            root = self.deleteNode(root,i)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        #返回修剪的二叉树节点\n",
    "        if not root: return root\n",
    "        if root.val == low:\n",
    "            root.left = None\n",
    "        elif root.val < low:\n",
    "            root = self.trimBST(root.right, low, high)\n",
    "        elif root.val > low:\n",
    "            root.left = self.trimBST(root.left,low, high) \n",
    "\n",
    "        if root.val == high:\n",
    "            root.right = None\n",
    "        elif root.val > high:\n",
    "            root = self.trimBST(root.left, low, high)\n",
    "        elif root.val < high:\n",
    "            root.right = self.trimBST(root.right,low, high)\n",
    "        return root \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        \n",
    "\n",
    "        def traverse(root): # 二叉树通用框架\n",
    "            if root is None:\n",
    "                return\n",
    "            \n",
    "            # 前序位置\n",
    "            root.left = traverse(root.left)\n",
    "            # 中序位置\n",
    "            root.right = traverse(root.right)\n",
    "            # 后序位置\n",
    "            print( root.val )\n",
    "            if root.val < low or root.val > high:\n",
    "                assert ((not root.left) or (not root.right)) #左右子节点有一个为空才合理\n",
    "                # 超出范围则return 有效子节点，否则return 自己\n",
    "                if root.left is None:\n",
    "                    return root.right\n",
    "                else:\n",
    "                    return root.left\n",
    "            else:\n",
    "                return  root\n",
    "\n",
    "        new_root = traverse(root)\n",
    "        return new_root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val>high:\n",
    "            return self.trimBST(root.left,low,high)\n",
    "        if root.val<low:\n",
    "            return self.trimBST(root.right,low,high)\n",
    "        if low<=root.val<=high:\n",
    "            root.left=self.trimBST(root.left,low,high)\n",
    "            root.right=self.trimBST(root.right,low,high)\n",
    "            return root            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            if root.left:\n",
    "                root.left = self.trimBST(root.left, low, high)\n",
    "            if root.val > high:\n",
    "                root = self.trimBST(root.left, low, high)\n",
    "            elif root.val < low:\n",
    "                root = self.trimBST(root.right, low, high)\n",
    "            if root and root.right:\n",
    "                root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        if root.val > high:\n",
    "            left = self.trimBST(root.left, low, high)\n",
    "            return left\n",
    "        elif root.val < low:\n",
    "            right = self.trimBST(root.right, low, high)\n",
    "            return right\n",
    "        else:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        # dfs表示修剪node为根的二叉搜素树\n",
    "        # 在修剪时要利用二叉搜索树的性质\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val < low:  # 修剪右边即可\n",
    "                return dfs(node.right)\n",
    "            if node.val > high:  # 修剪左边即可\n",
    "                return dfs(node.left)\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            return node\n",
    "        \n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        else:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def BST(root,low,high):\n",
    "            if not root: \n",
    "                return None\n",
    "\n",
    "            if root.val < low: \n",
    "                return BST(root.right, low, high)\n",
    "                \n",
    "            elif root.val > high:    \n",
    "                return BST(root.left, low, high)\n",
    "            \n",
    "            else:\n",
    "                par = root\n",
    "                root.left = BST(root.left, low, high)\n",
    "                root.right = BST(root.right, low, high)\n",
    "                return root\n",
    "       \n",
    "        return BST(root,low,high)\n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root: return root\n",
    "        # 处理头结点，让root移动到[L, R] 范围内，注意是左闭右开\n",
    "        while root and (root.val < low or root.val > high):\n",
    "            if root.val < low:  # 小于L往右走\n",
    "                root = root.right\n",
    "            else:  # 大于R往左走\n",
    "                root = root.left\n",
    "        # 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val < low:\n",
    "                cur.left = cur.left.right\n",
    "            cur = cur.left\n",
    "        # 此时root已经在[L, R] 范围内，处理右孩子大于R的情况\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val > high:\n",
    "                cur.right = cur.right.left\n",
    "            cur = cur.right\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            \n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            if root.val < low:\n",
    "                return right\n",
    "            elif root.val > high:\n",
    "                return left\n",
    "            else:\n",
    "                root.left = left\n",
    "                root.right = right\n",
    "                return root\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "            \n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "\n",
    "        elif root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        \n",
    "        else:\n",
    "\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "            return root  \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "#         if root == None:\n",
    "#             return None\n",
    "#         if root.val < low:         \n",
    "#             root.right = self.trimBST(root.right,low,high)\n",
    "#             return root.right\n",
    "#         elif root.val > high:\n",
    "#             root.left = self.trimBST(root.left, low, high)\n",
    "#             return root.left\n",
    "#         root.left = self.trimBST(root.left,low,high)\n",
    "#         root.right = self.trimBST(root.right,low,high)\n",
    "#         return root\n",
    "#################################################################\n",
    "# class Solution:\n",
    "#     def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "#         if root == None:\n",
    "#             return None\n",
    "#         if root.val < low:\n",
    "#             node = self.trimBST(root.right,low,high)\n",
    "#             return node\n",
    "#         if root.val > high:\n",
    "#             node = self.trimBST(root.left,low,high)\n",
    "#             return node\n",
    "#         root.left = self.trimBST(root.left,low,high)\n",
    "#         root.right = self.trimBST(root.right,low,high)\n",
    "#         return root\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right,low,high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left,low,high)\n",
    "        else:      #在范围内\n",
    "            root.left = self.trimBST(root.left,low,high)\n",
    "            root.right = self.trimBST(root.right,low,high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        elif root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        \n",
    "        else:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "            return root  \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        # # 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭\n",
    "        while root and (root.val < low or root.val > high):\n",
    "            if root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        \n",
    "        # 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val < low:\n",
    "                cur.left = cur.left.right\n",
    "            \n",
    "            cur = cur.left\n",
    "        \n",
    "        cur = root\n",
    "        # 此时root已经在[L, R] 范围内，处理右孩子大于R的情况\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val > high:\n",
    "                cur.right = cur.right.left\n",
    "            \n",
    "            cur = cur.right\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def delete(root, low, high, prenode, flag):\n",
    "            if not root:\n",
    "                return root\n",
    "            if root.val < low:\n",
    "                node = delete(root.right, low, high, prenode, flag)\n",
    "                if flag == 1:\n",
    "                    prenode.right = node\n",
    "                else:\n",
    "                    prenode.left = node\n",
    "                return node\n",
    "            if root.val > high:\n",
    "                node = delete(root.left, low, high, prenode, flag)\n",
    "                if flag == 1:\n",
    "                    prenode.right = node\n",
    "                else:\n",
    "                    prenode.left = node\n",
    "                return node\n",
    "            delete(root.left, low, high, root, 0)\n",
    "            delete(root.right, low, high, root, 1)\n",
    "            return root\n",
    "        ans = TreeNode()\n",
    "        ans.left = root\n",
    "        delete(ans.left, low, high, ans, 0)\n",
    "        return ans.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        \n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None \n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root \n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        if root.val < low:\n",
    "            right = self.trimBST(root.right, low, high)  # 寻找符合区间[low, high]的节点\n",
    "            return right\n",
    "        \n",
    "        if root.val > high:\n",
    "            left = self.trimBST(root.left, low, high)  # 寻找符合区间[low, high]的节点\n",
    "            return left\n",
    "        \n",
    "        root.left = self.trimBST(root.left, low, high)  # root.left接入符合条件的左孩子\n",
    "        root.right = self.trimBST(root.right, low, high)  # root.right接入符合条件的右孩子\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        '''\n",
    "        确认递归函数参数以及返回值：返回更新后剪枝后的当前root节点\n",
    "        '''\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        # 单层递归逻辑\n",
    "        if root.val < low:\n",
    "            # 若当前root节点小于左界：只考虑其右子树，用于替代更新后的其本身，抛弃其左子树整体\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            # 若当前root节点大于右界：只考虑其左子树，用于替代更新后的其本身，抛弃其右子树整体\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        \n",
    "        if low <= root.val <= high:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "            # 返回更新后的剪枝过的当前节点root\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        if root.val > low:\n",
    "            return self.trimBST(root.right, low, root.val)\n",
    "        \n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.right, low, root.val)\n",
    "\n",
    "    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\n",
    "        '''\n",
    "        确认递归函数参数以及返回值：返回更新后剪枝后的当前root节点\n",
    "        '''\n",
    "        # Base Case\n",
    "        if not root: return None\n",
    "\n",
    "        # 单层递归逻辑\n",
    "        if root.val < low:\n",
    "            # 若当前root节点小于左界：只考虑其右子树，用于替代更新后的其本身，抛弃其左子树整体\n",
    "            return self.trimBST(root.right, low, high)\n",
    "\n",
    "        if high < root.val:\n",
    "            # 若当前root节点大于右界：只考虑其左子树，用于替代更新后的其本身，抛弃其右子树整体\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        if low <= root.val <= high:\n",
    "            root.left = self.trimBST(root.left, low, root.val)\n",
    "            root.right = self.trimBST(root.right, root.val, high)\n",
    "            # 返回更新后的剪枝过的当前节点root\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\n",
    "    #     '''\n",
    "    #     迭代法\n",
    "    #     '''\n",
    "        if not root:return None\n",
    "        print(root.val)\n",
    "        while root and (root.val<low or root.val>high):\n",
    "            if root.val<low:root=root.right\n",
    "            elif root.val>high:root=root.left\n",
    "        cur=root\n",
    "        print(cur)\n",
    "        # 此时root已经在[low,high],处理左孩子元素小于low的情况\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val<low:\n",
    "                # 因为cur.left.right>cur.left(并删除了cur.left这个节点)\n",
    "                cur.left=cur.left.right\n",
    "            cur=cur.left\n",
    "        cur=root\n",
    "        # 此时root已经在[low,high] 范围内，处理右孩⼦⼤于high的情况\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val>high:\n",
    "                cur.right=cur.right.left        #右孩子大于high时（且cur.right.right也会大于high），删除该节点\n",
    "            cur=cur.right\n",
    "        return root\n",
    "\n",
    "    # # 递归法\n",
    "    # def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\n",
    "    #     if not root:return None\n",
    "    #     # 如果当前值小于low（左孩子一定小于low），则从右孩子开始递归\n",
    "    #     if root.val<low:\n",
    "    #         root=root.right     #把左节点裁掉\n",
    "    #         root= self.trimBST(root,low,high)\n",
    "    #     # 如果当前值大于high（右孩子一定大于high），则从左孩子开始递归\n",
    "    #     elif root.val>high:\n",
    "    #         root=root.left      #把右节点裁掉\n",
    "    #         root= self.trimBST(root,low,high)\n",
    "    #     elif low<=root.val<=high:\n",
    "    #         root.left=self.trimBST(root.left,low,high)      # root.left接⼊符合条件的左孩⼦\n",
    "    #         root.right=self.trimBST(root.right,low,high)    # root.right接⼊符合条件的右孩⼦\n",
    "    #     return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\r\n",
    "        if root == None:\r\n",
    "            return \r\n",
    "\r\n",
    "        if root.val < low:\r\n",
    "            return self.trimBST(root.right, low, high)\r\n",
    "        \r\n",
    "        if root.val > high:\r\n",
    "            return self.trimBST(root.left, low, high)\r\n",
    "        \r\n",
    "        root.left = self.trimBST(root.left, low, high)\r\n",
    "        root.right = self.trimBST(root.right, low, high)\r\n",
    "        return root\r\n",
    "        \r\n",
    "        # 自顶向下\r\n",
    "        if root == None:\r\n",
    "            return \r\n",
    "            \r\n",
    "        if root.val > high:\r\n",
    "            return self.trimBST(root.left, low, high)\r\n",
    "        if root.val < low:\r\n",
    "            return self.trimBST(root.right, low, high)\r\n",
    "        root.left = self.trimBST(root.left, low, high)\r\n",
    "        root.right = self.trimBST(root.right, low, high)\r\n",
    "        return root\r\n",
    "        \r\n",
    "        #自底向上\r\n",
    "        if root == None:\r\n",
    "            return \r\n",
    "\r\n",
    "        if root.val < low: # 裁剪\r\n",
    "            return self.trimBST(root.right, low, high)\r\n",
    "        elif root.val > high: # 裁剪\r\n",
    "            return self.trimBST(root.left, low, high)\r\n",
    "        else:\r\n",
    "            root.left = self.trimBST(root.left, low, high)\r\n",
    "            root.right = self.trimBST(root.right, low, high)\r\n",
    "            return root\r\n",
    "        \r\n",
    "        # 自顶向下\r\n",
    "        def dfs(root):\r\n",
    "            if root == None:\r\n",
    "                return None\r\n",
    "\r\n",
    "            if root.val > high: #二叉查找树的特性，不用调整节点顺序\r\n",
    "                return dfs(root.left)\r\n",
    "            elif root.val < low:\r\n",
    "                return dfs(root.right)\r\n",
    "            root.left = dfs(root.left)\r\n",
    "            root.right = dfs(root.right)\r\n",
    "\r\n",
    "            return root\r\n",
    "\r\n",
    "        return dfs(root)\r\n",
    "        \r\n",
    "        \r\n",
    "        def dfs(root, low, high):\r\n",
    "            if root == None:\r\n",
    "                return None\r\n",
    "            \r\n",
    "            if root.val > high:\r\n",
    "                return dfs(root.left, low, high)\r\n",
    "            elif root.val < low:\r\n",
    "                return dfs(root.right, low, high)\r\n",
    "            else:\r\n",
    "                root.left = dfs(root.left, low, high)\r\n",
    "                root.right = dfs(root.right, low, high)\r\n",
    "                return root\r\n",
    "\r\n",
    "        return dfs(root, low, high)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:\n",
    "        def dfs(head):\n",
    "            if not head: return \n",
    "            if not head.left and not head.right: return\n",
    "\n",
    "            print(head)\n",
    "            if head.left and head.left.val > high:\n",
    "                head.left = head.left.left\n",
    "                dfs(head)\n",
    "            if head.left and head.left.val < low:\n",
    "                head.left = head.left.right\n",
    "                dfs(head)\n",
    "            if head.right and  head.right.val < low:\n",
    "                head.right = head.right.right\n",
    "                dfs(head)\n",
    "            if head.right and head.right.val > high:\n",
    "                head.right = head.right.left\n",
    "                dfs(head)      \n",
    "                \n",
    "            if head.left:\n",
    "                dfs(head.left)\n",
    "            if head.right:\n",
    "                dfs(head.right)\n",
    "\n",
    "\n",
    "        dummy = TreeNode(-1, root)\n",
    "        dfs(dummy)\n",
    "        dummy = dummy.left\n",
    "        return dummy\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val >= low and root.val <= high:\n",
    "            print(self.trimBST(root.left, low, high))\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "            print(self.trimBST(root.right,low, high))\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "        elif root.val < low:\n",
    "            if root.right:\n",
    "                return self.trimBST(root.right, low, high)\n",
    "            else:\n",
    "                return None\n",
    "        elif root.val > high:\n",
    "            if root.left:\n",
    "                return self.trimBST(root.left, low, high)\n",
    "            else:\n",
    "                return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def deleteNode(cur):\n",
    "            if cur == None:\n",
    "                # 当前节点为空，直接返回None\n",
    "                return None\n",
    "            while cur.val < low or cur.val > high:\n",
    "                if cur.val < low:\n",
    "                    # 当前节点的值，比给的最小值要小，就需要把当前节点删除，并且比当前节点小的都要删除。\n",
    "                    # 有以下四种情况\n",
    "                    # 1:当前节点的左右子节点均为空，则直接删除节点，向上返回None\n",
    "                    if cur.left == None and cur.right == None:\n",
    "                        print(\"left==None and right==None\")\n",
    "                        return None\n",
    "                    # 2：当前节点的左节点为空，右节点不为空\n",
    "                    elif cur.left == None and cur.right != None:\n",
    "                        cur = cur.right\n",
    "                        print(cur)\n",
    "                    # 3:当前节点的左节点不为空，右节点为空，因为是二叉搜索树，所以当前节点比左子树中的所有值都要大，则需要把当前节点和左子树的所有节点都删除\n",
    "                    elif cur.left != None and cur.right == None:\n",
    "                        return None\n",
    "                    # 4:当前节点的左右节点均不为空，左子树需要删除，右子树\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        print(\"you\",cur)\n",
    "                if cur.val > high:\n",
    "                    if cur.left == None and cur.right == None:\n",
    "                        return None\n",
    "                    elif cur.left == None and cur.right != None:\n",
    "                        return None\n",
    "                    elif cur.left != None and cur.right == None:\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        print(\"zuo\",cur)\n",
    "            cur.left = deleteNode(cur.left)\n",
    "            cur.right = deleteNode(cur.right)\n",
    "            return cur\n",
    "        return deleteNode(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def deleteNode(cur):\n",
    "            if cur == None:\n",
    "                # 当前节点为空，直接返回None\n",
    "                return None\n",
    "            while cur.val < low or cur.val > high:\n",
    "                if cur.val < low:\n",
    "                    # 当前节点的值，比给的最小值要小，就需要把当前节点删除，并且比当前节点小的都要删除。\n",
    "                    # 有以下四种情况\n",
    "                    # 1:当前节点的左右子节点均为空，则直接删除节点，向上返回None\n",
    "                    if cur.left == None and cur.right == None:\n",
    "                        print(\"left==None and right==None\")\n",
    "                        return None\n",
    "                    # 2：当前节点的左节点为空，右节点不为空,需要继续判断右节点的值是否在范围外\n",
    "                    elif cur.left == None and cur.right != None:\n",
    "                        cur = cur.right\n",
    "                        print(cur)\n",
    "                    # 3:当前节点的左节点不为空，右节点为空，因为是二叉搜索树，所以当前节点比左子树中的所有值都要大，则需要把当前节点和左子树的所有节点都删除\n",
    "                    elif cur.left != None and cur.right == None:\n",
    "                        return None\n",
    "                    # 4:当前节点的左右节点均不为空，左子树需要删除，右子树的值需要继续判断是否在范围外\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        print(\"you\",cur)\n",
    "                if cur.val > high:\n",
    "                    if cur.left == None and cur.right == None:\n",
    "                        return None\n",
    "                    elif cur.left == None and cur.right != None:\n",
    "                        return None\n",
    "                    elif cur.left != None and cur.right == None:\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        print(\"zuo\",cur)\n",
    "            cur.left = deleteNode(cur.left)\n",
    "            cur.right = deleteNode(cur.right)\n",
    "            return cur\n",
    "        return deleteNode(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        # if root is None:\n",
    "        #     return None;\n",
    "        # 判断是否删除此节点\n",
    "        print(root)\n",
    "        while root is not None and (root.val < low or root.val > high): \n",
    "            if root.val < low:\n",
    "                root = root.right if root.right is not None else None\n",
    "                # return self.trimBST(root, low, high)\n",
    "            elif root.val > high:\n",
    "                root = root.left if root.left is not None else None\n",
    "        if root is None:\n",
    "            return None;\n",
    "\n",
    "        # 判断是否需要递归\n",
    "        if root.left is not None:\n",
    "            root.left = self.trimBST(root.left, low, high)\n",
    "        if root.right is not None:\n",
    "            root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        hide_node=TreeNode(None,root,root)\n",
    "        \n",
    "        crt_node=hide_node\n",
    "        while True:\n",
    "            print(crt_node.val,crt_node.left,crt_node.right)\n",
    "            if crt_node.left is None:\n",
    "                break\n",
    "            if crt_node.left.val < low:\n",
    "                crt_node.left=crt_node.left.right\n",
    "                if crt_node.val is None:\n",
    "                    crt_node.right=crt_node.left\n",
    "            else:\n",
    "                crt_node=crt_node.left\n",
    "        \n",
    "        crt_node=hide_node\n",
    "        while True:\n",
    "            print(crt_node.val,crt_node.left,crt_node.right)\n",
    "            if crt_node.right is None:\n",
    "                break\n",
    "            if crt_node.right.val > high:\n",
    "                crt_node.right=crt_node.right.left\n",
    "                if crt_node.val is None:\n",
    "                    crt_node.left=crt_node.right\n",
    "            else:\n",
    "                crt_node=crt_node.right\n",
    "\n",
    "        return hide_node.left\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def bst(root, low, high):\n",
    "            print(root)\n",
    "            if not root: return None\n",
    "            if root.val > high: return bst(root.left, low, high)\n",
    "            if root.val < low: return bst(root.right, low, high)\n",
    "\n",
    "            if root.left: root.left = bst(root.left, low, high)\n",
    "            if root.right: root.right = bst(root.right, low, high)\n",
    "            return root\n",
    "\n",
    "        dummy = TreeNode()\n",
    "        if not root: return None\n",
    "        dummy.right = root\n",
    "        dummy.right = bst(root, low, high)\n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root or low > high:\n",
    "            return None\n",
    "        print(root)\n",
    "        root = self.process(root, low, high)\n",
    "        return root\n",
    "\n",
    "    def process(self, node, l, r):\n",
    "        if not node:\n",
    "            return node\n",
    "        \n",
    "        if l <= node.val <= r:\n",
    "            node.left = self.process(node.left, l, r)\n",
    "            node.right = self.process(node.right, l, r)\n",
    "        else:\n",
    "            if node.val < l:\n",
    "                if node.right: #and node.right.val >= l:\n",
    "                    temp = self.process(node.right, l, r)\n",
    "                    node = None\n",
    "                    return temp\n",
    "                else:\n",
    "                    node = None\n",
    "                    return None\n",
    "            elif node.val > r:\n",
    "                if node.left: # and node.left.val <= r:\n",
    "                    temp = self.process(node.left, l, r)\n",
    "                    node = None\n",
    "                    return temp\n",
    "                else:\n",
    "                    node = None\n",
    "                    return None\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        '''\n",
    "        # 递归法：\n",
    "        # 1.确定递归函数的参数以及返回值\n",
    "        # 2.确定终止条件:修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了。\n",
    "        # 3.确定单层递归的逻辑:如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        return root\n",
    "        '''\n",
    "        # 迭代法：在剪枝的时候，可以分为三步：\n",
    "        # 1.将root移动到[L, R] 范围内，注意是左闭右闭区间\n",
    "        # 2.剪枝左子树\n",
    "        # 3.剪枝右子树\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        while root and (root.val < low or root.val >high):\n",
    "            if root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val < low:\n",
    "                cur.left = cur.left.right\n",
    "            cur = cur.left\n",
    "\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur .right and cur.right.val > high:\n",
    "                cur.right = cur.right.left\n",
    "            cur = cur.right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        while root and (root.val < low or root.val > high):  # 将根节点移动，使其符合[low, high]\n",
    "            if root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        \n",
    "        cur = root  # 处理左子树\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val < low:  # 左子树的值 小于 low, 左子树用其左子树的右子树代替\n",
    "                cur.left = cur.left.right\n",
    "            cur = cur.left\n",
    "\n",
    "        cur = root  # 处理右子树\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val > high:  # 右子树的值 大于 high, 右子树用其右子树的左子树代替\n",
    "                cur.right = cur.right.left\n",
    "            cur = cur.right\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        def f(i):\n",
    "            if i == None:\n",
    "                return None\n",
    "            if i.val < low:\n",
    "                return f(i.right)\n",
    "            elif i.val > high:\n",
    "                return f(i.left)\n",
    "            else:\n",
    "                i.left = f(i.left)\n",
    "                i.right = f(i.right)\n",
    "                return i\n",
    "        return f(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        dummy = TreeNode()\n",
    "        dummy.left = root\n",
    "\n",
    "\n",
    "        def trim(root): #suppose root satisfied\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left:\n",
    "                if root.left.val < low:\n",
    "                    root.left = root.left.right\n",
    "                    trim(root)\n",
    "                    return\n",
    "                if root.left.val > high:\n",
    "                    root.left = root.left.left\n",
    "                    trim(root)                  \n",
    "            if root.right:\n",
    "                if root.right.val < low:\n",
    "                    root.right = root.right.right\n",
    "                    trim(root)\n",
    "                    return\n",
    "                if root.right.val > high:\n",
    "                    root.right = root.right.left\n",
    "                    trim(root)    \n",
    "            trim(root.left)\n",
    "            trim(root.right)\n",
    "            return\n",
    "        trim(dummy)\n",
    "        return dummy.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        while root and(root.val<low or root.val> high):\n",
    "            if root.val<low:\n",
    "                root=root.right\n",
    "            else:\n",
    "                root=root.left\n",
    "        cur=root\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val<low:\n",
    "                cur.left=cur.left.right\n",
    "            cur=cur.left\n",
    "        cur=root\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val>high:\n",
    "                cur.right=cur.right.left\n",
    "            cur=cur.right\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''if not root:\n",
    "            return None\n",
    "        if root.val<low:\n",
    "            return self.trimBST(root.right,low,high)\n",
    "        elif root.val>high:\n",
    "            return self.trimBST(root.left,low,high)\n",
    "        root.left=self.trimBST(root.left,low,high)\n",
    "        root.right=self.trimBST(root.right,low,high)\n",
    "        return root'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "\n",
    "        return root        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        while root:\n",
    "            if root.val > high:\n",
    "                root = root.left\n",
    "            elif root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                break\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.left and cur.left.val < low:\n",
    "                cur.left = cur.left.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.right and cur.right.val > high:\n",
    "                cur.right = cur.right.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "    #     if not root:\n",
    "    #         return root\n",
    "    #     if root.val < low:\n",
    "    #         return self.trimBST(root.right, low, high)\n",
    "    #     if root.val > high:\n",
    "    #         return self.trimBST(root.left, low, high)\n",
    "    #     root.left = self.trimBST(root.left, low, high)\n",
    "    #     root.right = self.trimBST(root.right, low, high)\n",
    "    #     return root\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:  # 迭代\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        while root and (root.val < low or root.val > high):  # 将root移动到[low,high]之间\n",
    "            if root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "\n",
    "        cur = root\n",
    "\n",
    "        while cur:\n",
    "            while cur.left and cur.left.val < low:  # 去除左侧比low小的节点\n",
    "                cur.left = cur.left.right\n",
    "\n",
    "            cur = cur.left\n",
    "\n",
    "        cur = root\n",
    "        while cur:\n",
    "            while cur.right and cur.right.val > high:  # 去除右侧比high大的节点\n",
    "                cur.right = cur.right.left\n",
    "            cur = cur.right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        while root:\n",
    "            if root.val > high:\n",
    "                root = root.left\n",
    "            elif root.val < low:\n",
    "                root = root.right\n",
    "            else:\n",
    "                break\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.left and cur.left.val < low:\n",
    "                cur.left = cur.left.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.right and cur.right.val > high:\n",
    "                cur.right = cur.right.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val < low:\n",
    "            return self.trimBST(root.right, low, high)\n",
    "        if root.val > high:\n",
    "            return self.trimBST(root.left, low, high)\n",
    "        root.left = self.trimBST(root.left, low, high)\n",
    "        root.right = self.trimBST(root.right, low, high)\n",
    "        return root\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
